{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-colab"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/pathwaycom/pathway/blob/main/examples/notebooks/tutorials/bellman_ford.ipynb\" target=\"_parent\"><img src=\"https://pathway.com/assets/colab-badge.svg\" alt=\"Run In Colab\" class=\"inline\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "notebook-instructions",
      "source": [
        "# Installing Pathway with Python 3.10+\n",
        "\n",
        "In the cell below, we install Pathway into a Python 3.10+ Linux runtime.\n",
        "\n",
        "> **If you are running in Google Colab, please run the colab notebook (Ctrl+F9)**, disregarding the 'not authored by Google' warning.\n",
        "> \n",
        "> **The installation and loading time is less than 1 minute**.\n"
      ],
      "metadata": {}
    },
    {
      "cell_type": "code",
      "id": "pip-installation-pathway",
      "source": [
        "%%capture --no-display\n",
        "!pip install --prefer-binary pathway"
      ],
      "execution_count": null,
      "outputs": [],
      "metadata": {}
    },
    {
      "cell_type": "code",
      "id": "logging",
      "source": [
        "import logging\n",
        "\n",
        "logging.basicConfig(level=logging.CRITICAL)"
      ],
      "execution_count": null,
      "outputs": [],
      "metadata": {}
    },
    {
      "cell_type": "markdown",
      "id": "2",
      "metadata": {
        "lines_to_next_cell": 0
      },
      "source": [
        "# Real-Time Shortest Paths on Dynamic Networks with Bellman-Ford in Pathway\n",
        "This article explains step-by-step how the Bellman\u2013Ford algorithm may be implemented in Pathway.\n",
        "\n",
        "## Introduction\n",
        "\n",
        "The [Bellman-Ford algorithm](https://en.wikipedia.org/w/index.php?title=Bellman%E2%80%93Ford_algorithm&oldid=1088801570) computes the shortest paths from a single source vertex to all the other\n",
        "vertices in a weighted graph.\n",
        "A weighted graph is composed of a set of points, called *vertices*, which are connected via *edges*. Each edge is associated to a value, called either *weight* or *distance*.\n",
        "For instance, the set of all the cities and the roads which connect them form such a graph. In that example, the Bellman-Ford algorithm would help to find the fastest way, in terms of distance, to go from a given city to another.\n",
        "\n",
        "This article is also a perfect place to familiarize yourself with several constructs used in Pathway.\n",
        "\n",
        "## Code\n",
        "First things first - imports \ud83d\ude42"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "3",
      "metadata": {},
      "outputs": [],
      "source": [
        "import math\n",
        "\n",
        "import pathway as pw\n",
        "\n",
        "# To use advanced features with Pathway Scale, get your free license key from\n",
        "# https://pathway.com/features and paste it below.\n",
        "# To use Pathway Community, comment out the line below.\n",
        "pw.set_license_key(\"demo-license-key-with-telemetry\")\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "4",
      "metadata": {
        "lines_to_next_cell": 0
      },
      "source": [
        "### I/O Data\n",
        "The input is a weighted graph so it is natural to split representation of the data\n",
        "into two parts: Vertices and Edges. Their schemas:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "5",
      "metadata": {
        "lines_to_next_cell": 2
      },
      "outputs": [],
      "source": [
        "class Vertex(pw.Schema):\n",
        "    is_source: bool\n",
        "\n",
        "\n",
        "class Edge(pw.Schema):\n",
        "    u: pw.Pointer[Vertex]\n",
        "    v: pw.Pointer[Vertex]\n",
        "    dist: int"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "6",
      "metadata": {
        "lines_to_next_cell": 2
      },
      "source": [
        "These schemas have a natural interpretation. You can think of the `Edge` schema as of\n",
        "a blueprint of a table that has 3 columns: `u`, `v` (foreign keys) and `dist`.\n",
        "The output schema:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "7",
      "metadata": {
        "lines_to_next_cell": 2
      },
      "outputs": [],
      "source": [
        "class DistFromSource(pw.Schema):\n",
        "    dist_from_source: int"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "8",
      "metadata": {
        "lines_to_next_cell": 2
      },
      "source": [
        "*Note:* The schemas inherit from `pw.Schema` special class.\n",
        "\n",
        "*Note:* You might wonder why output schema has only one column `dist_from_source`.\n",
        "Actually, you can join schemas together to create a new one. And so, the output schema\n",
        " is `Vertex + DistFromSource`. (Look for that type annotation later in the code.)\n",
        "\n",
        "### The algorithm\n",
        "The Bellman-Ford algorithm performs some number of relaxations until it reaches a [fixed point](https://en.wikipedia.org/wiki/Fixed_point_(mathematics) \"Wipedia article of 'fixed point'\").\n",
        "\n",
        "#### Relaxations\n",
        "Each node checks if a path via it would make any so-far-optimal path to some other\n",
        "node shorter."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "9",
      "metadata": {},
      "outputs": [],
      "source": [
        "def bellman_ford_step(\n",
        "    vertices_dist: pw.Table[DistFromSource], edges: pw.Table[Edge]\n",
        ") -> pw.Table[DistFromSource]:\n",
        "    relaxed_edges = edges + edges.select(\n",
        "        dist_from_source=vertices_dist.ix(edges.u).dist_from_source + edges.dist\n",
        "    )\n",
        "    vertices_dist = vertices_dist.update_rows(\n",
        "        relaxed_edges.groupby(id=relaxed_edges.v).reduce(\n",
        "            dist_from_source=pw.reducers.min(relaxed_edges.dist_from_source),\n",
        "        )\n",
        "    )\n",
        "\n",
        "    return vertices_dist"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "10",
      "metadata": {
        "lines_to_next_cell": 0
      },
      "source": [
        "#### Fixed point\n",
        "The relaxations are iterated until a fixed point is reached. In this case, reaching a\n",
        "fixed point means that no new (shorter) path was found in the last iteration."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "11",
      "metadata": {},
      "outputs": [],
      "source": [
        "def bellman_ford(vertices: pw.Table[Vertex], edges: pw.Table[Edge]):\n",
        "    vertices_dist: pw.Table[DistFromSource] = vertices.select(\n",
        "        dist_from_source=pw.if_else(vertices.is_source, 0.0, math.inf)\n",
        "    )\n",
        "\n",
        "    fixed_point = pw.iterate(\n",
        "        lambda iterated, edges: dict(\n",
        "            iterated=bellman_ford_step(vertices_dist=iterated, edges=edges)\n",
        "        ),\n",
        "        # The `pw.iterate_universe` stanza informs iterate that `vertices_dist` grows with each loop iteration. Without it, the system assumes that iterations don't change the set of indices of a table.\n",
        "        iterated=pw.iterate_universe(vertices_dist),\n",
        "        edges=edges,\n",
        "    ).iterated\n",
        "\n",
        "    return fixed_point.join(vertices, fixed_point.id == vertices.id).select(\n",
        "        vertices.key, fixed_point.dist_from_source\n",
        "    )"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "12",
      "metadata": {
        "lines_to_next_cell": 0
      },
      "source": [
        "\n",
        " ## Tests\n",
        "\n",
        " Now, let's see the code in action. The following test case runs Bellman-Ford\n",
        "algorithm on a graph depicted below.\n",
        "\n",
        "<img src=\"/assets/content/tutorials/BellmanFordGraph.png\" alt=\"Graph image\" class=\"mx-auto\" />"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "13",
      "metadata": {},
      "outputs": [],
      "source": [
        "# a directed graph\n",
        "vertices = pw.debug.table_from_markdown(\n",
        "    \"\"\"\n",
        "  | key | is_source\n",
        "1 | 1   | True\n",
        "2 | 2   | False\n",
        "3 | 3   | False\n",
        "4 | 4   | False\n",
        "5 | 5   | False\n",
        "6 | 6   | False\n",
        "7 | 7   | False\n",
        "\"\"\"\n",
        ").with_id_from(pw.this.key)\n",
        "\n",
        "edges = pw.debug.table_from_markdown(\n",
        "    \"\"\"\n",
        "    | u  | v | dist\n",
        "11 | 1  | 2 | 100\n",
        "12 | 1  | 3 | 200\n",
        "13 | 1  | 4 | 300\n",
        "14 | 3  | 5 | 100\n",
        "15 | 3  | 6 | 500\n",
        "16 | 5  | 6 | 100\n",
        "17 | 6  | 3 | -50\n",
        "\"\"\"\n",
        ").with_columns(\n",
        "    u=vertices.pointer_from(pw.this.u),\n",
        "    v=vertices.pointer_from(pw.this.v),\n",
        ")"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "14",
      "metadata": {},
      "source": [
        "Pathway automatically reindexes the tables, so we need a key column of the `vertices` table and we need ask Pathway to reindex the table using those.\n",
        "In practice, Pathway uses pointers so the keys are automatically converted into pointers.\n",
        "\n",
        "For the edges, we have to convert the keys into their references in order to be able to use `vertices_dist.ix(edges.u)` as `ix` only works with pointers."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "15",
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "            | key | dist_from_source\n",
            "^YKEMVCM... | 1   | 0.0\n",
            "^MDY4T58... | 2   | 100.0\n",
            "^3AYGT7R... | 3   | 200.0\n",
            "^FGFPAGV... | 4   | 300.0\n",
            "^81GRBTV... | 5   | 300.0\n",
            "^P358CHY... | 6   | 400.0\n",
            "^CTWGSGG... | 7   | inf\n"
          ]
        }
      ],
      "source": [
        "pw.debug.compute_and_print(bellman_ford(vertices, edges))"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "16",
      "metadata": {},
      "source": [
        "That was a simple introduction to writing code and tests in Pathway.\n",
        "\n",
        "Feel free to take this code and experiment with it \ud83d\ude42  Do you see any possibility to\n",
        "improve the code? (What happens when there is a negative cycle in the graph?)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "17",
      "metadata": {},
      "source": [
        "## Summary\n",
        "The code above follows a pattern that is quite frequent when working with Pathway:\n",
        "- Define I/O data types\n",
        "- Define transformations on tables\n",
        "- Iterate the transformation until a fixed point is reached\n",
        "  - usually transforms the data by a simple one-liner.\n",
        "  - for example ```iterate(lambda foo, bar: {foo=fn(foo, bar), bar=bar}, foo=input_table_1, bar=input_table2).foo```"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3 (ipykernel)",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.11.14"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}